package org.example.day02;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO
 * <div>  一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。 </div> <div>  <br> </div> <div>  现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。 </div> <div>  <br> </div> <div>  例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：A任务，E任务，B任务，C任务，D任务。这里A和E任务都是没有依赖的，立即执行 </div> <div>  <span><br> </span>  </div> <span></span>
 *
 * 一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。
 * 现在给出多条任务依赖关系的规则，请输出任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。
 * 例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。
 * 那么执行任务的顺序由先到后是：A任务，E任务，B任务，C任务，D任务。这里A和E任务都是没有依赖的，立即执行
 * @date 2024/3/11 15:22
 */
public class test040 {
    // 执行任务的顺序
    public static List<Character> executeTasks(Map<Character, List<Character>> dependencies) {
        // 用于存储任务的入度
        Map<Character, Integer> inDegrees = new HashMap<>();
        // 初始化入度为0
        for (char task : dependencies.keySet()) {
            inDegrees.put(task, 0);
        }
        // 计算任务的入度
        for (List<Character> dependents : dependencies.values()) {
            for (char dependent : dependents) {
                inDegrees.put(dependent, inDegrees.getOrDefault(dependent, 0) + 1);
            }
        }

        // 用于存储无依赖任务的队列
        Queue<Character> queue = new PriorityQueue<>();
        for (char task : inDegrees.keySet()) {
            if (inDegrees.get(task) == 0) {
                queue.offer(task);
            }
        }

        List<Character> result = new ArrayList<>();
        // 贪婪策略执行任务
        while (!queue.isEmpty()) {
            char current = queue.poll();
            result.add(current);

            // 更新依赖于当前任务的任务的入度
            if (dependencies.containsKey(current)) {
                for (char dependent : dependencies.get(current)) {
                    inDegrees.put(dependent, inDegrees.get(dependent) - 1);
                    if (inDegrees.get(dependent) == 0) {
                        queue.offer(dependent);
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试数据
        Map<Character, List<Character>> dependencies = new HashMap<>();
        dependencies.put('A', new ArrayList<>());
        dependencies.put('B', Arrays.asList('A'));
        dependencies.put('C', Arrays.asList('A'));
        dependencies.put('D', Arrays.asList('B', 'C', 'E'));
        dependencies.put('E', new ArrayList<>());

        List<Character> result = executeTasks(dependencies);
        System.out.println("任务执行顺序：" + result); // 期望结果：[A, E, B, C, D]
    }
}